package br.ufmg.dcc.paa.collections;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Graph<T> {
	
	private Map<String, Vertex<T>> vertices;
	private Map<String, String> collapsed;
	
	public Graph() {
		vertices = new HashMap<>();
		collapsed = new HashMap<>();
	}
	
	public void add(String vertex) {
		if (vertices.containsKey(vertex))
			return;
		vertices.put(vertex, new Vertex<T>(vertex));
	}
	
	private Vertex<T> getNode(String u) {
		if (vertices.containsKey(u))
			return vertices.get(u);
		if (collapsed.containsKey(u))
			return vertices.get(collapsed.get(u));
		return null;
	}
	
	public boolean addEdge(String u, String v) {
		Vertex<T> vertexU = getNode(u);
		Vertex<T> vertexV = getNode(v);
		if (vertexU == null || vertexV == null || vertexU.equals(vertexV))
			return false;
		return vertexU.neighbors.add(vertexV);
	}
	
	public boolean addValue(String u, T value) {
		Vertex<T> vertexU = getNode(u);
		return vertexU != null ? vertexU.values.add(value) : false;
	}
	
	public boolean addAllValues(String u, Set<T> values) {
		boolean added = false;
		for (T value : values) {
			if (addValue(u, value))
				added = true;
		}
		return added;
	}
	
	public Set<T> getValues(String u) {
		Vertex<T> v = getNode(u);
		return v != null ? vertices.get(u).values : null;
	}
	
	public Set<String> getVertices() {
		return vertices.keySet();
	}
	
	public List<String> getNeighbors(String u) {
		Vertex<T> vertex = getNode(u);
		if (vertex == null)
			return null;
		
		List<String> neighbors = new LinkedList<>();
		for (Vertex<T> v : vertex.neighbors)
			neighbors.add(v.label);
		
		return neighbors;
	}
	
	public void collapse(List<String> cycle) {
		Set<Vertex<T>> neighbors = new HashSet<>();
		Set<T> values = new HashSet<>();
		neighbors.addAll(vertices.get(cycle.get(0)).neighbors);
		values.addAll(vertices.get(cycle.get(0)).values);

		String newLabel = cycle.get(0);
		for (int i=1; i < cycle.size(); i++) {
			newLabel += "," + cycle.get(i);
			neighbors.addAll(vertices.get(cycle.get(i)).neighbors);
			values.addAll(vertices.get(cycle.get(i)).values);
		}
		
		Vertex<T> newVertex = new Vertex<>(newLabel);
		newVertex.neighbors = neighbors;
		newVertex.values = values;
		
		for (String s : cycle) {
			Vertex<T> u = vertices.get(s);
			for (Vertex<T> v : vertices.values()) {
				if (v.equals(u))
					continue;
				if (v.neighbors.contains(u)) {
					v.neighbors.remove(u);
					v.neighbors.add(newVertex);
				}
			}
			vertices.remove(s);
			newVertex.neighbors.remove(u);
			collapsed.put(s, newLabel);
		}
		
		vertices.put(newLabel, newVertex);
	}
	
	//to use in searches
	public void initSearch() {
		for (Vertex<T> v : vertices.values()) {
			v.ancestor = null;
			v.visited = false;
		}
	}
	
	public void markAsVisited(String u) {
		if (!vertices.containsKey(u))
			return;
		vertices.get(u).visited = true;
	}
	
	public boolean isVisited(String u) {
		if (!vertices.containsKey(u))
			return false;
		return vertices.get(u).visited;
	}
	
	public void setAncestor(String u, String v) {
		if (!vertices.containsKey(u) || !vertices.containsKey(v))
			return;
		vertices.get(u).ancestor = v;
	}
	
	public String getAncestor(String u) {
		if (!vertices.containsKey(u))
			return null;
		return vertices.get(u).ancestor;
	}
	
	@Override
	public String toString() {
		return vertices.values().toString();
	}
	
	class Vertex<E> {
		private String label;
		private Set<E> values;
		private Set<Vertex<E>> neighbors;
		
		//to use in searches
		private boolean visited;
		private String ancestor;
		
		public Vertex(String label) {
			this.label = label;
			values = new HashSet<>();
			neighbors = new HashSet<>();
		}
		
		@Override
		public String toString() {
			return String.format("Vertex<%s, values=%s, neighbors=%s>", 
					             label, getValues(label), getNeighbors(label));
		}
	}
	
}
